\chapter{Codes de Goppa}

	\section{Définition d'un code de Goppa}
			
		Les codes de Goppa classiques sont des codes linéaires dont on connaît une borne inférieure de la distance minimale.
		Ce sont les codes utilisés dans le cryptosystème de McEliece qui va nous intéresser dans une troisième partie.
			
		\begin{defi} \label{goppa}
			On définit un code de Goppa  $ \mathbb{F}_{q}^{k} \rightarrow \mathbb{F}_{q}^{n} $  par son support L et un polynôme g définis par :
			 $$ \left \{
				\begin{array}{r c l}
					g &\in& \mathbb{F}_{q^{m}}[X] \ unitaire \ irr \acute{e} ductible \ sur \ \mathbb{F}_{q^{m}} \ de \ degr \acute{e} \ t \\
					L &=& (\alpha_{1},..,\alpha_{n})  \ d' \acute{e} l \acute{e} ments \ de \ \mathbb{F}_{q^{m}}
				\end{array}
			\right.  $$ 
			Dans la pratique on prend $n=q^{m}$ et $q=2$ pour manipuler des codes binaires.
			A partir de ces éléments, on définit le code de Goppa  $ \mathbf{C} $  par son syndrome  $ \mathbf{S}  $  comme :
			 $$ 
				\mathbf{C} = \{  y=(y_{1},..,y_{n}) \in \mathbb{F}_{q}^{n} / \mathbf{S}_{y}(x) = \sum_{i=1}^{n} \frac{y_{i}}{x-\alpha_{i}} = 0 \ mod \ g(x) \}
			 $$ 

		\end{defi}

		\begin{prop} \label{distance goppa}
			Le code de Goppa ainsi défini est de distance minimale  $ \mathbf{d} \geq t+1 $ .
			En effet en supposant qu'il existe un message  $ y = (y_{1},..,y_{n}) \in \mathbf{C} $  avec t ou moins coordonnées non nulles :
			 $$ 
				\sum_{i=1}^{n} \frac{y_{i}}{x-\alpha_{i}} = \frac{a(x)}{b(x)}= 0 \ mod \ g(x) \ fraction \ irr \acute{e} ductible
			 $$ 
			Donc g $ \mid $ a, ainsi a de degré supérieur ou égal à t.
			Or a de degré = nombre de coordonnées non nulles de y - 1  $ \leq t -1  $ 

			Par l'absurde le code de Goppa a une distance minimale  $ \mathbf{d} \geq t + 1 $ .
		\end{prop}

	\section{Construction de la matrice de parité}

		Nous souhaiterions donner à notre code de Goppa défini par son syndrome une structure plus visiblement linéaire. Nous allons construire sa matrice de parité.

		\begin{defi} \label{fi} \cite{04cc}
			Nous allons définir une famille de polynômes  $ \mathbf{f}_{i} $  inverses des  $ (x-\alpha_{i}) $ . Cela est possible car g étant irréductible,  $ \mathbb{F}[X]/g $  est un corps :
			 $$  \mathbf{f}_{i}(x)(x-\alpha_{i}) = 1 \ mod \ g(x) $$ 
			On a donc que :
			 $$ \forall y \in \mathbb{F}^{n} \ \mathbf{S}_{y}(x) = \sum_{i=1}^{n} \frac{y_{i}}{x-\alpha_{i}} = \sum_{i=1}^{n} \mathbf{f}_{i}(x)y_{i}  $$ 
		\end{defi}

		\begin{prop} \label{evalfi}
			Évaluons les  $ \mathbf{f}_{i} $  sous forme de fraction rationnelle :
			$$ \mathbf{f}_{i}(x) = \frac{1}{g(\alpha_{i})} \frac{g(x)-g(\alpha_{i})}{x-\alpha_{i}}  $$ 
			Maintenant tentons de les rendre polynomiaux, pour cela utilisons une formule de factorisation bien connue  :
			$$ x^{j} - \alpha_{i}^{j} = (x-\alpha_{i})\sum_{k=0}^{j-1} x^{k}\alpha_{i}^{j-1-k}$$
			On en déduit donc que :
			$$  \mathbf{f}_{i}(x) = \frac{1}{g(\alpha_{i})} \sum_{j=1}^{t} g_{j}\sum_{k=0}^{j-1} x^{k}\alpha_{i}^{j-1-k} 
			= \frac{1}{g(\alpha_{i})} \sum_{k=0}^{t-1} x^{k}\sum_{j=k+1}^{t} g_{j}\alpha_{i}^{j-1-k}$$
		\end{prop}

		Maintenant qu'on a montré leur existence et qu'on les a calculés, nous utilisons les fi pour construire la matrice de parité.
		Pour cela nous allons identifier un polynôme comme un vecteur de degré t.

		\begin{defi} \label{paritegoppa}
			On a donc des polynômes $(fi)_{1\leq i \leq n}$ de degrés t-1 que l'on va identifier comme des vecteurs colonnes de dimension t-1.
			$$ \forall y \in \mathbb{F}^{n} \ \mathbf{S}_{y}(x) = \sum_{i=1}^{n} \frac{y_{i}}{x-\alpha_{i}} = \sum_{i=1}^{n} \mathbf{f}_{i}(x)y_{i}$$
			$$ \forall y \in \mathbb{F}^{n} \  \mathbf{S}_{y}(x) =(f_{1}(x), ... , f_{n}(x))y $$
			On se retrouve donc avec une matrice de calcul de syndrome :
			$$ 
			\begin{pmatrix}
				\frac{1}{g(\alpha_{1})}g_{t} &  \frac{1}{g(\alpha_{2})}g_{t} & \cdots &  \frac{1}{g(\alpha_{n})}g_{t} \\
				\frac{1}{g(\alpha_{1})}(g_{t-1} + g_{t}\alpha_{1}) &  \frac{1}{g(\alpha_{2})}(g_{t-1} + g_{t}\alpha_{2}) & \cdots &  \frac{1}{g(\alpha_{n})}(g_{t-1} + g_{t}\alpha_{n}) \\
				\vdots & \vdots & \vdots & \vdots\\
				\frac{1}{g(\alpha_{1})}(g_{1} + ... +g_{t}\alpha_{1}^{t-1}) &  \frac{1}{g(\alpha_{2})}(g_{1} + ... +g_{t}\alpha_{1}^{t-1}) & \cdots &  \frac{1}{g(\alpha_{n})}(g_{1} + ... +g_{t}\alpha_{1}^{t-1}) \\
			\end{pmatrix}
			$$
			Pour construire la matrice de parité, comme seul le noyau nous intéresse, nous allons simplifier cette matrice et poser H matrice de parité égale à :
			$$
			\begin{pmatrix}
				\frac{1}{g(\alpha_{1})} &  \frac{1}{g(\alpha_{2})} & \cdots &  \frac{1}{g(\alpha_{n})} \\
				\frac{1}{g(\alpha_{1})}g_{t}\alpha_{1} &  \frac{1}{g(\alpha_{2})}g_{t}\alpha_{2} & \cdots &  \frac{1}{g(\alpha_{n})}g_{t}\alpha_{n}\\
				\vdots & \vdots & \vdots & \vdots\\
				\frac{1}{g(\alpha_{1})}g_{t}\alpha_{1}^{t-1} &  \frac{1}{g(\alpha_{2})}g_{t}\alpha_{2}^{t-1} & \cdots &  \frac{1}{g(\alpha_{n})}g_{t}\alpha_{n}^{t-1} \\
			\end{pmatrix}
			$$
		\end{defi}

		Maintenant que nous possédons sa matrice de parité, le codage est possible. 
		La construction de G matrice génératrice de notre code de Goppa s'effectue simplement.
		N'étant pas spécifique aux codes de Goppa, l'algorithme utilisé est décrit plus tard.

	\section{Équation clef}

		Nous sommes dorénavant dotés des outils algébriques nécessaires au codage de nos messages.
		Nous allons maintenant étudier comment les décoder.

		\begin{defi} \label{localisateur} \cite{finiasz}
			Nous allons introduire le polynôme localisateur d'erreurs $\sigma$, qui par sa connaissance permet de déterminer l'emplacement des erreurs dans le message. Dans l'hypothèse d'un nombre d'erreurs permettant la correction $deg(\sigma)\leq\frac{t}{2}$.
			$$ \forall y \in \mathbf{C} \ , \ \sigma_{y+\epsilon}(x) = \prod_{\epsilon_{i} \ne 0} (x-\alpha_{i}) \ mod \ g(x)$$
		\end{defi}

		L'enjeu du décodage va être de déterminer le polynôme localisateur d'erreurs pour un message donné et d'en déterminer les racines.

		\begin{defi} \label{evaluateur}
			Nous allons définir le polynôme évaluateur d'erreurs $ \omega$ défini par :
			$$ \omega(x) = \sigma(x)\mathbf{S}_{y}(x) \ mod \ g(x)$$
			Par construction $deg(\omega)<\frac{t}{2}$.
			L'intérêt de ce second polynôme est de mettre en évidence l'équation clef du décodage :
			$$ \omega(x) = \sigma(x)\mathbf{S}_{y}(x) + k(x)g(x) $$
		\end{defi}


	\section{Résolution de l'équation clef}

		La résolution de cette équation clef est la détermination de $\sigma$.
		Pour cela il existe plusieurs techniques, nous étudierons celle utilisant l'algorithme d'Euclide.
		L'algorithme d'Euclide étendu tel qu'utilisé est redonné plus tard.

		\begin{prop} \label{unicite} \cite{goppa}
			On a unicité de la résolution de l'équation clef pour les polynômes $\sigma$ et $\omega$ de degrés  $deg(\sigma) \leq \frac{t}{2}$ et $ deg(\omega) < \frac{t}{2} $ à un scalaire près.
			On suppose de plus que les deux polynômes sont de degrés minimum, c'est à dire premiers entre eux.
			En effet, soient $(\sigma_{1},\omega_{1})$ et $(\sigma_{2},\omega_{2})$ deux solutions de degrés inférieurs à $\frac{t}{2}$.
			On a :
			$$ \omega_{1}(x) = \sigma_{1}(x)\mathbf{S}_{y}(x) \ mod \ g(x) \ , \ \omega_{2}(x) = \sigma_{2}(x)\mathbf{S}_{y}(x) \ mod \ g(x) $$
			$$ \omega_{1}(x)\sigma_{2}(x) = \sigma_{1}(x)\mathbf{S}_{y}(x)\sigma_{2}(x) \ mod \ g(x) \ , \ \omega_{2}(x)\sigma_{1}(x) = \sigma_{2}(x)\mathbf{S}_{y}(x)\sigma_{1}(x) \ mod \ g(x) $$
			Ainsi :
			$$ \omega_{1}(x)\sigma_{2}(x) - \omega_{2}(x)\sigma_{1}(x) = 0 \ mod \ g(x) $$
			Or le degré du polynôme du membre de gauche est de degré $\leq t-1$.
			Ce polynôme est donc nul et $ \omega_{1}(x)\sigma_{2}(x) = \omega_{2}(x)\sigma_{1}(x) $.
			Avec l'hypothèse de degrés minimums, on a égalité des couples à un scalaire près.
		\end{prop}

		Il s'agit désormais d'expliciter un tel couple solution pour accéder au polynôme localisateur d'erreurs.
		Pour cela nous utilisons l'algorithme d'Euclide étendu.

		\begin{prop} \label{existence}
			On définit des suites $(r_{n},s_{n},t_{n})$ telles que $ r_{n}(x) = s_{n}(x)\mathbf{S}_{y}(x) + t_{n}(x)g(x) $.
			La relation de récurrence est donnée par l'algorithme d'Euclide étendu.
			Comme les solutions de l'équation clef existent par construction, on sait que le PGCD de $g(x)$ et $\mathbf{S}_{y}(x)$ a un degré strictement inférieur à $\frac{t}{2}$.

			Ainsi on sait que la suite des $r_{n}(x)$ a des degrés décroissants et $\exists s / deg(r_{s}(x)) < \frac{t}{2},$ avec $deg(r_{s-1}(x)) \geq \frac{t}{2}$.
			Montrons que $deg(s_{s}(x)) \leq \frac{t}{2}$.
			$$ s_{i+1}(x) = s_{i-1} - (r_{i-1}(x) \ div  \ r_{i}(x))s_{i}(x) $$
			Donc :
			$$ deg(s_{s}) = \sum_{i=2}^{s-1} deg(r_{i-1}(x) \ div  \ r_{i}(x)) = deg(r_{1}(x)) - deg(r_{s-1}(x)) \leq \frac{t}{2}$$
		\end{prop}

		L'algorithme d'Euclide étendu, stoppé au bon moment concernant les contraintes sur les degrés donne une solution particulière.
		Grâce à l'unicité, nous avons déterminé le polynôme localisateur d'erreur dont la détermination des racines caractérise le vecteur d'erreur du message.
		Pour cela nous utiliserons au choix, l'algorithme de Berlekamp-Hensel ou une recherche exhaustive.